////#include<iostream>
////using namespace std;
////int main()
////{
////	int a, b;
////	cin >> a >> b;
////	while (a <= b)
////	{
////		int k = a;
////		int t = sqrt(k);
////		if ( t*t != k)
////		{
////			a++;
////			continue;
////		}
////		if (k / 10 == 0)
////		{
////			cout << k << endl;
////			a++;
////		}
////		else
////		{
////			int tmp = 10;
////			int left = k / tmp;
////			int right = k % tmp;
////			int flag = 0;
////			while (left)
////			{
////				if (right != 0)
////				{
////					int l = sqrt(left);
////					int r = sqrt(right);
////					if (l * l == left && r * r == right)
////					{
////						flag = 1;
////						break;
////					}
////				}
////				tmp *= 10;
////				left = k / tmp;
////				right = k % tmp;
////			}
////			if (flag)
////				cout << a << endl;
////			a++;
////		}
////		
////	}
////}
////#include<iostream>
////using namespace std;
////long long map[501][501] = { 0 };
////int main()
////{
////	long long n, k;
////	cin >> n >> k;
////	map[1][1] = 1;
////	map[2][1] = 2;
////	int i = 3;
////	for (i; i <= n; i++)
////	{
////		int j = 1;
////		for (j; j <= k&&j<=n; j++)
////		{
////			map[i][j] = (map[i-1][j]+ map[i][j-1]*(i-1)) % 12345;
////			if (i % 2 == 0)
////				map[i][j] = (map[i][j] + map[i - 1][j - 1]) % 12345;
////
////		}
////	}
////	cout << map[n][k];
////}
//#include<iostream>
//#include<stack>
//using namespace std;
//int main()
//{
//	int n;
//	cin >> n;
//	int i = 1;
//	for (i; i < n; i++)
//	{
//		int j = 1;
//		for (j; j <= i; j++)
//		{
//			int a = i;
//			int b = j;
//			stack<int> l;
//			while (a >= n)
//			{
//				l.push(a % n);
//				a /= n;
//			}
//			l.push(a);
//			while (!l.empty())
//			{
//				if (l.top() < 10)
//					cout << char('0' + l.top());
//				else
//					cout << char('A' + l.top() - 10);
//				l.pop();
//			}
//			cout << '*';
//			while (b >= n)
//			{
//				l.push(b % n);
//				b /= n;
//			}
//			l.push(b);
//			while (!l.empty())
//			{
//				if (l.top() < 10)
//					cout << char('0' + l.top());
//				else
//					cout << char('A' + l.top() - 10);
//				l.pop();
//			}
//			cout << '=';
//			int ct = i * j;
//			stack<int> s;
//			while (ct >= n)
//			{
//				s.push(ct % n);
//				ct /= n;
//			}
//			s.push(ct);
//			while (!s.empty())
//			{
//				if (s.top() < 10)
//					cout << char('0' + s.top());
//				else
//					cout << char('A' + s.top() - 10);
//				s.pop();
//			}
//			cout << ' ';
//		}
//		cout << endl;
//	}
//}
//#include<iostream>
//using namespace std;
//int main()
//{
//	long long a, b, c;
//	cin >> a >> b >> c;
//	long long sum = 0;
//	long long ct = 0;
//	long long t = 5*a + 2*b;
//	ct = c / t;
//	c -= ct * t;
//	int i = 1;
//	while(i)
//	{
//		if (i > 7)
//		{
//			ct++;
//			i = 1;
//		}
//		if (i  <= 5)
//			sum += a;
//		else
//			sum += b;
//		if (sum >= c)
//			break;
//		i++;
//	}
//	cout << i+ct*7;
//}
//#include<iostream>
//#include<vector>
//#include<utility>
//
//using namespace std;
//
//
//int find_ifcan(int& count,vector<pair<int, pair<int, int>>>& v,int now, int N,int visit[])
//{
//	if (count >= N)
//		return 1;
//	int i = 0;
//	for (i;i < N; i++)
//	{
//		if (visit[i] == 0)
//		{
//			visit[i] = 1;
//			if (v[i].first + v[i].second.first >= now)
//			{
//				count++;
//				if (find_ifcan(count,v,max(now,v[i].first)+v[i].second.second, N,visit))
//					return 1;
//				count--;
//			}
//			visit[i] = 0;
//		}
//	}
//	return 0;
//}
//int main()
//{
//	int T;
//	cin >> T;
//	while (T--)
//	{
//		int N;
//		cin >> N;
//		
//		int flag = 1;
//		int i = 0;
//		vector<pair<int, pair<int, int>>> v;
//		for (i; i < N; i++)
//		{
//			int t, d, l;
//			cin >> t >> d >> l;
//			pair<int, pair<int, int>> p;
//			p.first = t;
//			p.second.first = d;
//			p.second.second = l;
//			v.push_back(p);
//		}
//		int visit[11] = { 0 };
//		int count = 0;
//		flag = find_ifcan(count,v,0, N,visit);
//		if (flag)
//			cout << "YES" << endl;
//		else
//			cout << "NO" << endl;
//	}
//}
//#include<iostream>
//using namespace std;
//int main()
//{
//	long long N;
//	cin >> N;
//	long long ct = 0;
//	long long i = 1;
//	for (i; i <= N; i++)
//	{
//		long long k = i;
//		int flag = 1;
//		while (k)
//		{
//			if (flag)
//			{
//				if ((k % 10) % 2 == 0)
//					break;
//			}
//			else
//			{
//				if ((k % 10) % 2 == 1)
//					break;
//			}
//			flag = !flag;
//			k /= 10;
//		}
//		if (k == 0)
//			ct++;
//	}
//	cout << ct;
//}
//#include<iostream>
//using namespace std;
//string get_result(int n, string s)
//{
//
//	while (n--)
//	{
//		s.insert(s.begin(), '0');
//		int i = 1;
//		for (i; i < s.size(); i++)
//		{
//			int j = s[i] - '0';
//			j *= 2;
//			if (j >= 10)
//			{
//				s[i] = j % 10+'0';
//				int z = i - 1;
//				while (z >= 0 && s[z] == 9)
//				{
//					s[z] = '0';
//					z--;
//				}
//				if (z >= 0)
//					s[z]++;
//				else
//				{
//					s.insert(s.begin(), '1');
//				}
//			}
//			else
//			{
//				s[i] = j + '0';
//			}
//		}
//	}
//	int k = 0;
//	while (k<s.size()&&s[k] == '0')
//		k++;
//	if (k == s.size())
//		return "0";
//	string ss(s.begin() + k, s.end());
//	return ss;
//}
//int main()
//{
//	long long n;
//	string d;
//	cin >> n >> d;
//	int i = d.find('.');
//	if (i == string::npos)
//	{
//		//cout << d;
//		cout << get_result(n, d);
//	}
//	else
//	{
//		string s1(d.begin(), d.begin() + i);
//		string s2(d.begin() + i + 1, d.end());
//
//		int sz = s2.size();
//		//cout << s1 << ' ' << s2;
//		s1=get_result(n,s1);
//		s2=get_result(n,s2);
//		if (s2.size()<=sz&&s2[0] >= '5')
//		{
//			if (s2.size() < sz)
//				cout << s1;
//			else
//			{
//				int i = s1.size() - 1;
//				while (i >= 0 && s1[i] == '9')
//				{
//					s1[i--] = '0';
//				}
//				if (i < 0)
//					s1.insert(s1.begin(), '1');
//				else
//					s1[i]++;
//				cout << s1;
//			}
//
//		}
//		else
//		{
//			string ss(s2.begin(), s2.begin() + s2.size()-sz);
//			if (s2[s2.size()-sz] >= '5')
//			{
//				int i = ss.size() - 1;
//				while (i >= 0 && ss[i] == '9')
//				{
//					ss[i--] = '0';
//				}
//				if (i < 0)
//					ss.insert(ss.begin(), '1');
//				else
//					ss[i]++;
//			}
//			s2 = ss;
//			sz = s2.size();
//			int l = s1.size()-1;
//			while (sz--)
//			{
//				int j = s2[sz] - '0';
//				int k = l--;
//				int c = s1[k] - '0';
//				if (j + c < 10)
//					s1[k] = j + c + '0';
//				else
//				{
//					s1[k] = j + c - 10 + '0';
//					k--;
//					while (k>=0&&s1[k] == '9')
//					{
//						s1[k] = '0';
//						k--;
//					}
//					if (k < 0)
//						s1.insert(s1.begin(), '1');
//					else
//					s1[k]++;
//				}
//			}
//			cout << s1;
//		}
//		
//	}
//}
//#include<iostream>
//using namespace std;
//#include<queue>
//queue<int> q1;
//queue<int> q2;
//int main()
//{
//	int n, m;
//	cin >> n >> m;
//	while (n--)
//	{
//		int x;
//		cin >> x;
//		q1.push(x);
//	}
//	while (m--)
//	{
//		int x;
//		cin >> x;
//		q2.push(x);
//	}
//	int flag = 1;
//	int ct = 0;
//	while (flag&&!q1.empty() && !q2.empty())
//	{
//		flag = 0;
//		int a, b;
//		a = q1.front();
//		q1.pop();
//		b = q2.front();
//		q2.pop();
//		if (a == b)
//			flag = 1;
//		else
//		{
//			if (a < b)
//			{
//				while (a!=b&&!q1.empty() && !q2.empty())
//				{
//					if (a < b)
//					{
//						a += q1.front();
//						q1.pop();
//					}
//					else
//					{
//						b += q2.front();
//						q2.pop();
//					}
//					ct++;
//				}				
//				if (a > b)
//				{
//					while (a != b && !q2.empty())
//					{
//						b += q2.front();
//						q2.pop();
//						ct++;
//					}
//				}
//				if (a < b)
//				{
//					while (a != b && !q1.empty())
//					{
//						a += q1.front();
//						q1.pop();
//						ct++;
//					}
//				}
//				if (a == b)
//					flag = 1;
//			}
//			else
//			{
//				while (a != b && !q1.empty() && !q2.empty())
//				{
//					if (a < b)
//					{
//						a += q1.front();
//						q1.pop();
//					}
//					else
//					{
//						b += q2.front();
//						q2.pop();
//					}
//					ct++;
//				}
//				if (a > b)
//				{
//					while (a != b && !q2.empty())
//					{
//						b += q2.front();
//						q2.pop();
//						ct++;
//					}
//				}
//				if (a < b)
//				{
//					while (a != b && !q1.empty())
//					{
//						a += q1.front();
//						q1.pop();
//						ct++;
//					}
//				}
//				if (a == b)
//					flag = 1;
//				if (a == b)
//					flag = 1;
//			}
//		}
//	}
//	if (flag)
//		cout << ct;
//	else
//		cout << "0";
//}
//#include<iostream>
//using namespace std;
//int main()
//{
//    int n = 5;
//    int ct = 0;
//    while (n--)
//    {
//        int x;
//        cin >> x;
//        int a = x / 1000;
//        int b = x % 1000 / 100;
//        int c = x % 100 / 10;
//        int d = x % 10;
//        if (a == c && d - b == 1)
//            ct++;
//    }
//    cout << ct;
//}
//#include<iostream>
//using namespace std;
//long long func(string s)
//{
//	long long dp[5005][5005] = { 0 };
//	int arr[5005] = { 0 };
//	long long ans = 0;
//	int all, p = 0;
//	for (int i = 0, t = 0; i < s.size(); i++) {
//		if (s[i] == ')') {
//			if (--t < 0)p++;
//			arr[p]++;
//		}
//		else if (t++ < 0)t = 1;
//	}
//	dp[0][1] = 1, all = arr[0];
//	for (int i = 1; i <= p; i++) {
//		all += arr[i];
//		for (int j = 1; j <= all - arr[i] + 1; j++) {
//			dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 1000000007;
//		}
//	}
//	for (int i = 1; i <= all - arr[p] + 1; i++)ans = (ans + dp[p][i]) % 1000000007;
//	return ans;
//}
//string reverse(string s)
//{
//	string t;
//	string::reverse_iterator it = s.rbegin();
//	while (it != s.rend())
//	{
//		if (*it == '(')
//			t += ')';
//		else
//			t += '(';
//		it++;
//	}
//	return t;
//}
//int main()
//{
//	string s;
//	cin >> s;
//	long long a = func(s);
//	long long b = func(reverse(s));
//	cout << a * b;
//}
//#include<iostream>
//using namespace std;
//int main()
//{
//	long long n;
//	long long t;
//	cin >> n >> t;
//	string s;
//	cin >> s;
//	long long x = 1;
//	while (x < n)
//	{
//		x=x << 1;
//		
//	}
//	t = t % x;
//	for (int i = 0; i < t; i++)
//	{
//		for (int j = n - 1; j >= 1; j--)
//			s[j] = (s[j] - '0') ^ (s[j - 1] - '0') + '0';
//	}
//	cout << s;
//}
//#include<iostream>
//using namespace std;
//long long arr[30] = { 0 };
//#include<vector>
//vector<long long> v;
//int main()
//{
//	int n;
//	cin >> n;
//	int i;
//	long long mm = 0;
//	for (i = 0; i < n; i++)
//	{
//		long long x;
//		cin >> x;
//		v.push_back(x);
//		mm = max(mm, x);
//	}
//	int ct= n;
//	int pre1, pre2;
//	for (pre1 = 1, pre2 = 1; pre1 <= 10e6&&pre1<=mm; pre1++, pre2++)
//	{
//		int p1 = pre1, p2 = pre2;
//		int cc = 0;
//		for (int j = 0; j < n && j < 30; j++)
//		{
//			if (j == 0 || j == 1)
//			{
//				if (v[j] != p1)
//					cc++;
//			}
//			else
//			{
//				int now = p1 + p2;
//				p1 = p2;
//				p2 = now;
//				if (v[j] != now)
//					cc++;
//			}
//			
//		}
//		ct = min(ct, cc);
//	}
//	cout << ct + max(0, n - 30);
//}
//#include<iostream>
//using namespace std;
//int arr[26] = { 0 };
//int main()
//{
//	int n, m;
//	cin >> n >> m;
//	string s1;
//	string s2;
//	cin >> s1 >> s2;
//	for (auto i : s2)
//	{
//		arr[i - 'a']++;
//	}
//	string s;
//	int j = 0;
//	string::iterator it = s1.begin();
//	while (j < 26 && it != s1.end())
//	{
//		//cout << s << endl;
//		while (j<26&&arr[j] == 0)
//			j++;
//		while (j < 26 && it != s1.end() && *it <= (j + 'a'))
//		{
//			s.push_back(*it);
//			it++;
//
//		}
//		if(j < 26 && it != s1.end() && *it >= (j + 'a'))
//		{
//			while (arr[j]--)
//			{
//				s.push_back(j + 'a');
//			}
//				j++;
//		}
//	}
//	while (it != s1.end())
//	{
//		s.push_back(*it);
//		it++;
//	}
//	if (j < 26)
//	{
//		while (arr[j] == 0)
//			j++;
//		while (j<26&&arr[j]--)
//		{
//			s.push_back(j + 'a');
//		}
//	}
//	cout << s;
//}